﻿// 506 最长上升子序列II.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;
/*
http://oj.daimayuan.top/course/22/problem/647


给定一个长度为 n的数组 a1,a2,…,an
，问其中的最长上升子序列的长度。也就是说，我们要找到最大的 m 以及数组 p1,p2,…,pm，满足 1≤p1<p2<⋯<pm≤n
 并且 ap1<ap2<⋯<apm。

输入格式
第一行一个数字 n。

接下来一行 n个整数 a1,a2,…,an。

输出格式
一个数，表示答案。

样例输入
6
3 7 4 2 6 8
样例输出
4
数据规模
所有数据保证 1≤n≤100000,1≤ai≤109。
*/


const int N = 100010;
int a[N];
int dp[N]; int dplen = 0;
int n;



int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for (int i = 1; i <= n; i++) {
		int x = a[i];
		int l = 0; int r = dplen;
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (dp[mid] <= x) l = mid;
			else r = mid - 1;
		}
		if (dp[l] == x) l--;
		
		if (0 == dp[l + 1]) {
			dp[l + 1] = x;
		}
		else {
			dp[l + 1] = min(x, dp[l + 1]);
		}

		dplen = max(dplen, l + 1);
	}
	

	cout << dplen << endl;
	return 0;
}

 